#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <windows.h>
#include "attendance.h"

// ========== 全局变量 ==========
// 使用树结构代替原来的链表结构，提高查找效率
Student *studentRoot = NULL;        // 学生信息二叉搜索树的根节点，按学号排序
ClassRecord *recordRoot = NULL;     // 课程记录二叉搜索树的根节点，按课程编号排序

// ========== 控制台颜色设置 ==========
/**
 * 设置控制台输出文本颜色
 * @param color 颜色代码（Windows控制台颜色常量）
 * 10=绿色，11=青色，12=红色，14=黄色，7=默认白色
 */
void setColor(int color) {
    SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), color);
}

// ========== 学生树操作辅助函数 ==========

/**
 * 将新学生节点插入二叉搜索树
 * @param root 当前子树根节点
 * @param newStudent 要插入的新学生节点
 * @return 插入后的子树根节点
 * 采用递归方式实现，保持二叉搜索树性质：左子树所有节点学号 < 根节点学号 < 右子树所有节点学号
 */
Student* insertStudent(Student* root, Student* newStudent) {
    // 基准情况：找到插入位置
    if (root == NULL) {
        return newStudent;
    }
    
    // 比较学号，决定插入左子树还是右子树
    int cmp = strcmp(newStudent->id, root->id);
    if (cmp < 0) {
        // 新学号小于当前节点学号，插入左子树
        root->left = insertStudent(root->left, newStudent);
    } else if (cmp > 0) {
        // 新学号大于当前节点学号，插入右子树
        root->right = insertStudent(root->right, newStudent);
    }
    // 如果学号相同，这里选择忽略（不插入重复学号），在实际调用前已做检查
    
    return root;
}

/**
 * 中序遍历学生二叉搜索树
 * @param root 当前遍历的子树根节点
 * 中序遍历顺序：左子树 -> 根节点 -> 右子树
 * 由于二叉搜索树的性质，中序遍历结果按学号升序排列
 */
void inOrderTraversal(Student* root) {
    if (root != NULL) {
        inOrderTraversal(root->left);           // 递归遍历左子树
        printf("%-10s %-10s %-10s\n", root->id, root->name, root->className);  // 访问当前节点
        inOrderTraversal(root->right);          // 递归遍历右子树
    }
}

/**
 * 在学生树中查找指定学号的节点
 * @param root 当前查找的子树根节点
 * @param id 要查找的学生学号
 * @return 找到的学生节点指针，未找到返回NULL
 * 利用二叉搜索树性质进行高效查找，时间复杂度O(log n)
 */
Student* findStudentNode(Student* root, char *id) {
    if (root == NULL) return NULL;  // 基准情况：树为空或查找失败
    
    int cmp = strcmp(id, root->id);
    if (cmp == 0) {
        // 找到目标节点
        return root;
    } else if (cmp < 0) {
        // 目标学号小于当前节点学号，在左子树中继续查找
        return findStudentNode(root->left, id);
    } else {
        // 目标学号大于当前节点学号，在右子树中继续查找
        return findStudentNode(root->right, id);
    }
}

/**
 * 查找学生树中的最小节点（最左节点）
 * @param root 查找起始节点
 * @return 最小节点指针
 * 在二叉搜索树中，最小节点是最左边的节点
 * 用于删除操作中寻找替代节点
 */
Student* findMinStudent(Student* root) {
    if (root == NULL) return NULL;
    // 一直向左遍历，直到没有左子节点
    while (root->left != NULL) {
        root = root->left;
    }
    return root;
}

/**
 * 从学生树中删除指定学号的节点
 * @param root 当前子树根节点
 * @param id 要删除的学生学号
 * @return 删除后的子树根节点
 * 处理三种情况：
 * 1. 叶子节点：直接删除
 * 2. 只有一个子节点：用子节点替代
 * 3. 有两个子节点：用中序后继替代，然后删除中序后继
 */
Student* deleteStudentNode(Student* root, char *id) {
    if (root == NULL) return NULL;  // 基准情况：未找到要删除的节点
    
    int cmp = strcmp(id, root->id);
    if (cmp < 0) {
        // 目标学号在左子树中，递归在左子树中删除
        root->left = deleteStudentNode(root->left, id);
    } else if (cmp > 0) {
        // 目标学号在右子树中，递归在右子树中删除
        root->right = deleteStudentNode(root->right, id);
    } else {
        // 找到要删除的节点
        // 情况1：只有右子节点或没有子节点
        if (root->left == NULL) {
            Student* temp = root->right;
            free(root);             // 释放当前节点内存
            return temp;            // 返回右子节点作为新的子树根
        } 
        // 情况2：只有左子节点
        else if (root->right == NULL) {
            Student* temp = root->left;
            free(root);             // 释放当前节点内存
            return temp;            // 返回左子节点作为新的子树根
        }
        
        // 情况3：有两个子节点
        // 找到右子树中的最小节点（中序后继）
        Student* temp = findMinStudent(root->right);
        // 用中序后继的数据覆盖当前节点数据
        strcpy(root->id, temp->id);
        strcpy(root->name, temp->name);
        strcpy(root->className, temp->className);
        // 在右子树中删除中序后继节点
        root->right = deleteStudentNode(root->right, temp->id);
    }
    return root;
}

// ========== 课程记录树操作 ==========

/**
 * 将新课程记录插入二叉搜索树
 * @param root 当前子树根节点
 * @param newRecord 要插入的新课程记录
 * @return 插入后的子树根节点
 * 按课程编号排序：左子树课程编号 < 根节点课程编号 < 右子树课程编号
 */
ClassRecord* insertClassRecord(ClassRecord* root, ClassRecord* newRecord) {
    if (root == NULL) {
        return newRecord;    // 基准情况：找到插入位置
    }
    
    // 按课程编号比较
    if (newRecord->lessonNo < root->lessonNo) {
        // 新课次编号较小，插入左子树
        root->left = insertClassRecord(root->left, newRecord);
    } else if (newRecord->lessonNo > root->lessonNo) {
        // 新课次编号较大，插入右子树
        root->right = insertClassRecord(root->right, newRecord);
    }
    // 课程编号相同时忽略（在调用前已做检查）
    
    return root;
}

/**
 * 在课程记录树中查找指定课程编号的节点
 * @param root 当前查找的子树根节点
 * @param lessonNo 要查找的课程编号
 * @return 找到的课程记录节点指针，未找到返回NULL
 * 利用二叉搜索树性质进行高效查找
 */
ClassRecord* findClassRecordNode(ClassRecord* root, int lessonNo) {
    if (root == NULL) return NULL;  // 基准情况：查找失败
    
    if (lessonNo == root->lessonNo) {
        // 找到目标课程记录
        return root;
    } else if (lessonNo < root->lessonNo) {
        // 目标课程编号较小，在左子树中查找
        return findClassRecordNode(root->left, lessonNo);
    } else {
        // 目标课程编号较大，在右子树中查找
        return findClassRecordNode(root->right, lessonNo);
    }
}

// ========== 学生管理函数 ==========

/**
 * 添加新学生到系统中
 * 从用户输入获取学生信息，创建新节点并插入学生树
 * 包含输入验证和重复学号检查
 */
void addStudent() {
    // 动态分配内存创建新学生节点
    Student *newStudent = (Student*)malloc(sizeof(Student));
    if (newStudent == NULL) {
        printf("内存分配失败！\n");
        return;
    }
    
    // 获取用户输入
    printf("请输入 学号 姓名 班级：");
    // 使用字段宽度限制防止缓冲区溢出
    if (scanf("%19s %19s %19s", newStudent->id, newStudent->name, newStudent->className) != 3) {
        printf("输入格式错误！\n");
        free(newStudent);    // 输入失败时释放内存
        return;
    }
    
    // 初始化新节点的左右指针
    newStudent->left = NULL;
    newStudent->right = NULL;
    
    // 检查学号是否已存在（避免重复）
    if (findStudentNode(studentRoot, newStudent->id) != NULL) {
        printf("学号已存在！\n");
        free(newStudent);    // 学号重复时释放内存
        return;
    }
    
    // 将新学生插入学生树
    studentRoot = insertStudent(studentRoot, newStudent);
    
    // 成功提示
    setColor(10);    // 绿色
    printf("学生添加成功！\n");
    setColor(7);     // 恢复默认颜色
}

/**
 * 显示所有学生信息
 * 通过中序遍历学生树，按学号顺序显示学生列表
 */
void showStudents() {
    // 检查学生树是否为空
    if (studentRoot == NULL) {
        printf("没有学生记录！\n");
        return;
    }
    
    // 显示表头
    setColor(11);    // 青色
    printf("\n%-10s %-10s %-10s\n", "学号", "姓名", "班级");
    setColor(7);     // 恢复默认颜色
    
    // 中序遍历显示所有学生（按学号排序）
    inOrderTraversal(studentRoot);
}

/**
 * 查找学生（外部接口）
 * @param id 要查找的学生学号
 * @return 找到的学生节点指针
 * 包装内部查找函数，提供统一接口
 */
Student* findStudent(char *id) {
    return findStudentNode(studentRoot, id);
}

/**
 * 删除指定学号的学生
 * @param id 要删除的学生学号
 * 包含存在性检查和删除操作
 */
void deleteStudent(char *id) {
    // 先检查学生是否存在
    if (findStudent(id) == NULL) {
        printf("未找到学号为 %s 的学生！\n", id);
        return;
    }
    
    // 从学生树中删除指定学号的学生
    studentRoot = deleteStudentNode(studentRoot, id);
    
    // 成功提示
    setColor(12);    // 红色
    printf("已删除学号 %s\n", id);
    setColor(7);     // 恢复默认颜色
}

// ========== 考勤管理函数 ==========

/**
 * 开始某次课程的考勤
 * @param lessonNo 课程编号
 * 为指定课程创建考勤记录，遍历所有学生进行考勤输入
 * 使用非递归中序遍历学生树，避免递归深度问题
 */
void startAttendance(int lessonNo) {
    // 检查该课程记录是否已存在（避免重复考勤）
    if (findClassRecordNode(recordRoot, lessonNo) != NULL) {
        printf("该课程记录已存在！\n");
        return;
    }
    
    // 创建新的课程记录节点
    ClassRecord *newRecord = (ClassRecord*)malloc(sizeof(ClassRecord));
    if (newRecord == NULL) {
        printf("内存分配失败！\n");
        return;
    }
    
    // 初始化课程记录
    newRecord->lessonNo = lessonNo;
    newRecord->attList = NULL;      // 考勤链表初始为空
    newRecord->left = NULL;
    newRecord->right = NULL;
    
    printf("\n第%d节课考勤：\n", lessonNo);
    
    // 使用栈模拟中序遍历学生树（非递归方式）
    Student* stack[100];    // 栈数组，存储节点指针
    int top = -1;           // 栈顶指针
    Student* current = studentRoot; // 当前遍历节点
    int studentCount = 0;   // 记录考勤学生计数
    
    // 非递归中序遍历学生树
    while (current != NULL || top >= 0) {
        // 遍历到最左节点，路径上的节点全部入栈
        while (current != NULL) {
            if (top >= 99) {    // 栈溢出检查
                printf("栈溢出！\n");
                break;
            }
            stack[++top] = current;  // 节点入栈
            current = current->left; // 移动到左子节点
        }
        
        // 处理栈顶节点
        if (top >= 0) {
            current = stack[top--];  // 节点出栈
            
            // 对当前学生进行考勤输入
            int status;
            printf("学号:%s 姓名:%s 出勤输入1 缺勤输入0: ", current->id, current->name);
            // 输入验证
            if (scanf("%d", &status) != 1 || (status != 0 && status != 1)) {
                printf("输入无效，默认为缺勤\n");
                status = 0;  // 输入无效时默认设为缺勤
            }
            
            // 创建考勤记录节点
            Attendance *newAttendance = (Attendance*)malloc(sizeof(Attendance));
            if (newAttendance != NULL) {
                strcpy(newAttendance->studentId, current->id);  // 复制学号
                newAttendance->status = status;                 // 设置考勤状态
                // 头插法将考勤记录插入链表
                newAttendance->next = newRecord->attList;
                newRecord->attList = newAttendance;
                studentCount++;     // 成功考勤学生数加1
            }
            
            // 移动到右子节点
            current = current->right;
        }
    }
    
    // 将新课程记录插入课程记录树
    recordRoot = insertClassRecord(recordRoot, newRecord);
    
    // 考勤完成提示
    setColor(10);    // 绿色
    printf("考勤记录完成！共记录 %d 名学生\n", studentCount);
    setColor(7);     // 恢复默认颜色
}

/**
 * 显示某次课程的考勤情况
 * @param lessonNo 课程编号
 * 查找指定课程，遍历其考勤链表，显示每个学生的考勤状态
 */
void showLessonAttendance(int lessonNo) {
    // 查找课程记录
    ClassRecord *cr = findClassRecordNode(recordRoot, lessonNo);
    if (cr == NULL) {
        printf("未找到第%d节课记录！\n", lessonNo);
        return;
    }
    
    // 检查考勤链表是否为空
    Attendance *a = cr->attList;
    if (a == NULL) {
        printf("该课程没有考勤记录！\n");
        return;
    }
    
    // 显示表头
    setColor(14);    // 黄色
    printf("\n第%d节课考勤情况：\n", lessonNo);
    printf("%-10s %-10s %-10s\n", "学号", "姓名", "状态");
    setColor(7);     // 恢复默认颜色
    
    // 遍历考勤链表，显示每个学生的考勤情况
    int count = 0;
    while (a != NULL) {
        // 根据学号查找学生信息
        Student *student = findStudent(a->studentId);
        if (student != NULL) {
            // 显示学生基本信息
            printf("%-10s %-10s ", student->id, student->name);
            // 根据考勤状态显示不同颜色的结果
            if (a->status) { 
                setColor(10);       // 绿色显示出勤
                printf("出勤\n"); 
            } else { 
                setColor(12);       // 红色显示缺勤
                printf("缺勤\n"); 
            }
            setColor(7);            // 恢复默认颜色
            count++;                // 记录显示的学生数
        }
        a = a->next;    // 移动到下一个考勤记录
    }
    printf("共显示 %d 条记录\n", count);
}

/**
 * 显示指定学生的所有考勤记录
 * @param id 学生学号
 * 遍历所有课程记录，查找该学生的考勤情况
 * 使用非递归方式遍历课程记录树
 */
void showStudentAttendance(char *id) {
    // 检查学生是否存在
    Student *student = findStudent(id);
    if (student == NULL) {
        printf("未找到学号为 %s 的学生！\n", id);
        return;
    }
    
    printf("\n学号 %s 姓名 %s 的考勤情况：\n", student->id, student->name);
    
    // 使用栈非递归遍历课程记录树
    ClassRecord* stack[100];
    int top = -1;
    ClassRecord* current = recordRoot;
    int recordCount = 0;    // 找到的考勤记录计数
    
    while (current != NULL || top >= 0) {
        // 遍历左子树
        while (current != NULL) {
            if (top >= 99) {    // 栈溢出检查
                printf("栈溢出！\n");
                break;
            }
            stack[++top] = current;  // 课程节点入栈
            current = current->left; // 移动到左子课程
        }
        
        // 处理当前课程节点
        if (top >= 0) {
            current = stack[top--];  // 课程节点出栈
            
            // 在当前课程的考勤链表中查找该学生的记录
            Attendance *a = current->attList;
            while (a != NULL) {
                if (strcmp(a->studentId, id) == 0) {
                    // 找到该学生在本课程的考勤记录
                    printf("第%d节课: ", current->lessonNo);
                    if (a->status) {
                        setColor(10);   // 绿色显示出勤
                        printf("出勤\n");
                    } else {
                        setColor(12);   // 红色显示缺勤
                        printf("缺勤\n");
                    }
                    setColor(7);        // 恢复默认颜色
                    recordCount++;      // 找到的记录数加1
                    break; // 找到记录后跳出内层循环（每个课程只应有一条该学生的记录）
                }
                a = a->next;    // 检查下一个考勤记录
            }
            
            // 移动到右子课程
            current = current->right;
        }
    }
    
    // 结果显示
    if (recordCount == 0) {
        printf("该学生没有任何考勤记录！\n");
    } else {
        printf("共找到 %d 条考勤记录\n", recordCount);
    }
}

/**
 * 统计某次课程的出勤率
 * @param lessonNo 课程编号
 * 计算指定课程的出勤人数、缺勤人数和出勤率
 */
void countLessonRate(int lessonNo) {
    // 查找课程记录
    ClassRecord *cr = findClassRecordNode(recordRoot, lessonNo);
    if (cr == NULL) {
        printf("未找到第%d节课记录！\n", lessonNo);
        return;
    }
    
    // 统计变量初始化
    int total = 0, present = 0;
    Attendance *a = cr->attList;
    
    // 遍历考勤链表进行统计
    while (a != NULL) {
        total++;            // 总人数加1
        if (a->status) present++;   // 出勤人数加1
        a = a->next;        // 移动到下一个考勤记录
    }
    
    // 输出统计结果
    if (total > 0) {
        printf("第%d节课出勤统计：\n", lessonNo);
        printf("总人数: %d\n", total);
        printf("出勤人数: %d\n", present);
        printf("缺勤人数: %d\n", total - present);
        printf("出勤率: %.2f%%\n", (double)present / total * 100);
    } else {
        printf("该课程没有考勤记录！\n");
    }
}

/**
 * 统计指定学生的缺勤次数
 * @param id 学生学号
 * 遍历所有课程记录，统计该学生的缺勤次数和总体出勤率
 */
void countStudentAbsence(char *id) {
    // 检查学生是否存在
    Student *student = findStudent(id);
    if (student == NULL) {
        printf("未找到学号为 %s 的学生！\n", id);
        return;
    }
    
    // 统计变量初始化
    int absenceCount = 0;   // 缺勤次数
    int totalLessons = 0;   // 总课程数
    
    // 使用栈非递归遍历课程记录树
    ClassRecord* stack[100];
    int top = -1;
    ClassRecord* current = recordRoot;
    
    while (current != NULL || top >= 0) {
        // 遍历左子树
        while (current != NULL) {
            if (top >= 99) break;   // 栈溢出检查
            stack[++top] = current; // 课程节点入栈
            current = current->left; // 移动到左子课程
        }
        
        // 处理当前课程节点
        if (top >= 0) {
            current = stack[top--]; // 课程节点出栈
            totalLessons++;         // 总课程数加1
            
            // 在当前课程中查找该学生的考勤记录
            Attendance *a = current->attList;
            while (a != NULL) {
                if (strcmp(a->studentId, id) == 0) {
                    // 找到记录，检查是否缺勤
                    if (a->status == 0) {
                        absenceCount++; // 缺勤次数加1
                    }
                    break; // 找到记录后跳出内层循环
                }
                a = a->next;    // 检查下一个考勤记录
            }
            
            // 移动到右子课程
            current = current->right;
        }
    }
    
    // 输出统计结果
    printf("学号 %s 姓名 %s 的缺勤统计：\n", student->id, student->name);
    printf("总课程数: %d\n", totalLessons);
    printf("缺勤次数: %d\n", absenceCount);
    if (totalLessons > 0) {
        // 计算并显示出勤率
        printf("出勤率: %.2f%%\n", (double)(totalLessons - absenceCount) / totalLessons * 100);
    }
}